/*
Source : https://leetcode.com/problems/combination-sum-iv/
Author : nflush@outlook.com
Date   : 2016-07-26
*/

/*
377. Combination Sum IV

    Total Accepted: 948
    Total Submissions: 2500
    Difficulty: Medium

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

Subscribe to see which companies asked this question
*/
class Solution {
private:
    int gcd(int a, int b){
        if(b == 0){
            return a;
        }
        return gcd(b, a % b);
    }
    static bool compare(const int a, const int b){
        return a < b;
    }

public:
    int combinationSum4(vector<int>& nums, int target) {
        if (nums.size() == 0) return 0; // [] 2
        std::sort(nums.begin(), nums.end(), compare);
        if (nums[0] > target) return 0; // [3,6,9] 2
        int ggd = nums[0];
        for (int i = 1; ggd != 1 && i < nums.size() && nums[i] <= target; i++){
            ggd = gcd(nums[i], ggd);
        }
        if (ggd != 1){
            if ((target %ggd) != 0) return 0; // [3,6,9] 8
            for (int i = 0; i < nums.size(); i++){
                nums[i] /= ggd;
            }
            target /= ggd;
        }
        vector<int> ret(target+1, 0);
        int sum = 0;
        for (int i =nums[0]; i <= target; i++){
            sum = 0;
            // [1,2,3] 8 f(8) = f(7) +1 ,f(6) +2, f(5) +3
            // sum(8) = sum(7) + sum(6) + sum(5)
            for (int j = 0; j < nums.size(); j++){
                if (i == nums[j]){
                    sum++;
                    break;
                } else if (i < nums[j]){
                    break;
                } else {
                    sum += ret[i - nums[j]]; 
                }
            }
            ret[i] = sum;
        }
        return ret[target];
    }
};

